from typing import List


class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid1[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        islands = {}
        island_idx = 0
        for i in range(m):
            for j in range(n):
                if grid1[i][j] == 1 and (i, j) not in islands:
                    island = {(i, j)}
                    queue = [(i, j)]
                    while queue:
                        i1, j1 = queue.pop()
                        for i2, j2 in neighbors(i1, j1):
                            if grid1[i2][j2] == 1 and (i2, j2) not in island:
                                island.add((i2, j2))
                                queue.append((i2, j2))
                    for i1, j1 in island:
                        islands[(i1, j1)] = island_idx
                    island_idx += 1

        ans = 0
        visited = set()
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1 and (i, j) not in visited:
                    island_lst = set()
                    include = True
                    queue = [(i, j)]
                    while queue:
                        i1, j1 = queue.pop()
                        if (i1, j1) not in islands:
                            include = False
                        else:
                            island_lst.add(islands[(i1, j1)])
                        for i2, j2 in neighbors(i1, j1):
                            if grid2[i2][j2] == 1 and (i2, j2) not in visited:
                                visited.add((i2, j2))
                                queue.append((i2, j2))
                    if len(island_lst) == 1 and include:
                        ans += 1

        return ans


if __name__ == "__main__":
    # 3
    print(Solution().countSubIslands(
        grid1=[[1, 1, 1, 0, 0], [0, 1, 1, 1, 1], [0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1]],
        grid2=[[1, 1, 1, 0, 0], [0, 0, 1, 1, 1], [0, 1, 0, 0, 0], [1, 0, 1, 1, 0], [0, 1, 0, 1, 0]]))

    # 2
    print(Solution().countSubIslands(
        grid1=[[1, 0, 1, 0, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 0, 1, 0, 1]],
        grid2=[[0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 1]]))
